//
// Created by 123 on 2024/3/24.
//
#include <iostream>

using namespace std;

#define MaxSize 3


int Graph[MaxSize][MaxSize]={
        {0,6,13},
        {10,0,4},
        {5,99999,0}
};
int path[MaxSize][MaxSize]={
        {-1,0,0},
        {1,-1,1},
        {2,-1,-1},
};

void floyd(){
//    把矩阵跑 n 回
    for (int k = 0; k < MaxSize; ++k) {
        for (int i = 0; i < MaxSize; ++i) {
            for (int j = 0; j < MaxSize; ++j) {
                if(Graph[i][j]>Graph[i][k]+Graph[k][j]){
                    Graph[i][j]=Graph[i][k]+Graph[k][j];
                    path[i][j]=path[k][j];
//                    path[i][j]=k;
                }
            }
        }
    }
}
int main(){
    floyd();
    for (int i = 0; i < MaxSize; ++i) {
        for (int j = 0; j < MaxSize; ++j) {
            cout<<Graph[i][j]<<"    ";
        }
        cout<<endl;
    }
    cout<<"--------------------------------"<<endl;
    for (int i = 0; i < MaxSize; ++i) {
        for (int j = 0; j < MaxSize; ++j) {
            cout<<path[i][j]<<"    ";
        }
        cout<<endl;
    }
}


